package middle;

import java.util.ArrayList;
import java.util.List;

public class Solution_29 {
    public int divide(int dividend, int divisor) {
        boolean flag = (dividend >= 0 && divisor > 0) || (dividend < 0 && divisor < 0);
        dividend = dividend <= 0 ? dividend : Math.negateExact(dividend);
        divisor = divisor <= 0 ? divisor : Math.negateExact(divisor);
        int count = 0;
        List<Integer> list = new ArrayList<>();
        list.add(divisor);
        while (dividend <= divisor) {
            for (int i = list.size() - 1; i >= 0; i--) {
                if (dividend <= list.get(i)) {
                    dividend -= list.get(i);
                    count -= (i + 1);
                    if (i == list.size() - 1) {
                        list.add(list.get(i) + list.get(0));
                    }
                }
            }
        }
        return flag ? count == Integer.MIN_VALUE ? Integer.MAX_VALUE : Math.negateExact(count) : count;
    }

    public static void main(String[] args) {
        Solution_29 model = new Solution_29();
        System.out.println(model.divide(10, 3));
        System.out.println(model.divide(7, -3));
        System.out.println(model.divide(Integer.MIN_VALUE, 4));
        System.out.println(model.divide(Integer.MAX_VALUE, 1));
        System.out.println(model.divide(Integer.MAX_VALUE, -1));
        System.out.println(model.divide(Integer.MIN_VALUE, 1));
        System.out.println(model.divide(Integer.MIN_VALUE, -1));
        System.out.println(Integer.MAX_VALUE);
        System.out.println(Integer.MIN_VALUE);
    }
}
